﻿//3143. 正方形中的最多点数
//给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。
//如果一个正方形的中心在(0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。
//请你返回 合法 正方形中可以包含的 最多 点数。
//如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
//正方形的边长可以为零。



class Solution {
public:
    int maxPointsInsideSquare(vector<vector<int>>& points, string s)
    {
        int n = points.size();
        auto check = [&](int edge)->bool
        {
            unordered_set<char> cnt;
            int r = edge / 2;
            for (int i = 0; i < n; i++)
            {
                if (abs(points[i][0]) <= r && abs(points[i][1]) <= r)
                {
                    if (cnt.count(s[i]))
                    {
                        return false;
                    }
                    else
                    {
                        cnt.insert(s[i]);
                    }
                }
            }
            return true;
        };
        long long left = 0, right = INT_MAX;
        while (left <= right)
        {
            long long mid = left + (right - left) / 2;
            if (check(mid))
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        int edge = left - 1;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int r = edge / 2;
            if (abs(points[i][0]) <= r && abs(points[i][1]) <= r)
            {
                ans++;
            }
        }
        return ans;
    }
};